//
//  二叉搜索树.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/1/30.
//

import UIKit



class BinarySearchTree<E: Equatable & Comparable>: BinaryTree<E>{
    
//    typealias E = Q
    
    /// 添加元素
    /// - Parameter elem: 元素
    func add(_ elem: E) {
        
        if rootNode == nil {
            let node = creatNode(elem, parent: nil)
            rootNode = node
            count += 1
            addAfterNode(node)
            return
        }
        
        var node = rootNode
        var parent = rootNode
        var result = 0
        while node != nil, let temp = node {
            result = compare(a: elem, b: temp.val)
            parent = temp
            if result < 0 {
                node = temp.left
            } else if result > 0 {
                node = temp.right
            } else {
                node?.val = elem
                return
            }
        }
        let newNode = creatNode(elem, parent: parent)
        if result < 0 {
            parent?.left = newNode
        } else {
            parent?.right = newNode
        }
        count += 1
//        多态，让子类实现的方
        addAfterNode(newNode)
        
    }
    
    func creatNode(_ elem: E, parent: TreeNode<E>?) -> TreeNode<E> {
        return TreeNode(elem: elem, parent: parent)
    }
    
    func addAfterNode(_ nodel: TreeNode<E>) {
        
    }
    
    func afterRemove(_ node: TreeNode<E>) {
        
    }
    
    /// 删除元素
    /// - Parameter elem: 元素
    func remove(_ elem: E) {
        let node = getNode(elem, rootNode)
        remove(node)
    }
    
    private func remove(_ node: TreeNode<E>?) {
        guard var node = node else {
            return
        }
        count -= 1
        // 度为2的接地那
        if node.hasTowChildNode(), let successor = successor(node) {
            // 覆盖内容
            node.val = successor.val
            // 处理将要删除的的节点
            node = successor
        }
        // 要取代的节点
        let replaceNode = node.left != nil ? node.left : node.right
        
        if let replaceNode = replaceNode {
            replaceNode.parent = node.parent
            if node.parent == nil {
                rootNode = replaceNode
            } else if node.parent?.left == node {
                node.parent?.left = replaceNode
            } else {
                node.parent?.right = replaceNode
            }
            afterRemove(node)
        } else { // 叶子节点
            if node == node.parent?.left {
                node.parent?.left = nil
            } else {
                node.parent?.right = nil
            }
            afterRemove(node)
        }
    }
    /// 是否有某个元素节点
    /// - Parameter elem: 节点值
    /// - Returns: 结果
    func contains(_ elem: E) -> Bool {
        getNode(elem, rootNode) != nil
    }
}

extension BinarySearchTree {
    private func compare(a: E, b: E) -> Int {
        if a == b {
            return 0
        } else if a > b {
            return 1
        } else {
            return -1
        }
    }
    func creatBinarySearchTree(_ arrray: [E]) {
        arrray.forEach {
            add($0)
        }
    }
}
